package tencent

type LRUCache struct {
	keyMap        map[int]*lruNode
	head          *lruNode //访问顺序
	tail          *lruNode //访问顺序
	totalCapacity int
}

type lruNode struct {
	pre   *lruNode
	after *lruNode
	key   int
	val   int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		totalCapacity: capacity,
		keyMap:        map[int]*lruNode{},
	}
}

//若没查询到 返回-1
//查询到了 返回值。 且要更新访问顺序。 注意边界情况， 链表只有一个元素， 访问头尾结点
func (this *LRUCache) Get(key int) int {
	if node, ok := this.keyMap[key]; ok {
		//头指针不更新了
		if node.key == this.head.key {
			return node.val
		}
		pre := node.pre
		after := node.after
		if pre != nil {
			pre.after = after
		}
		if after != nil {
			after.pre = pre
		}
		node.pre = nil
		node.after = this.head
		if this.head != nil {
			this.head.pre = node
		}
		this.head = node
		if this.tail.key == node.key { //边界情况， 若是队尾元素， 跟新尾部指针。
			this.tail = pre //若是访问tail 且pre是nil。那说明只有一个元素， 会满足 node.val == this.head.val，走不到这里
		}
		return node.val
	}
	return -1
}

//1. 若存在则更新
//2 若不存在
//2.1 若缓存满了， 删除最后队未元素。且删除keyMap中尾部的key对于元素
//注意边界情况： head 和tail 是同一元素。此时使用的容量是1
func (this *LRUCache) Put(key int, value int) {
	val := this.Get(key)
	//存在更新key的结点值。 key的访问顺序再get方法中设置了
	if val != -1 {
		//更新值
		this.keyMap[key].val = value
		return
	}
	//不存在新增结点
	node := &lruNode{
		after: this.head,
		key:   key,
		val:   value,
	}
	//判断容量
	if len(this.keyMap) == this.totalCapacity {
		delete(this.keyMap, this.tail.key) //淘汰最后一个访问的元素
		if len(this.keyMap) == 0 {         //边界情况。
			this.head, this.tail = nil, nil
		} else {
			pre := this.tail.pre
			pre.after = nil
			this.tail = pre
		}
	}
	//头部插入
	if len(this.keyMap) == 0 { //边界情况
		this.tail = node
	} else {
		this.head.pre = node
	}
	this.head = node
	this.keyMap[key] = node //新加入的key
}
